package middle;

import java.util.HashMap;
import java.util.TreeMap;

/**
 * 105.重建二叉树
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *
 * */

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BuildTree {
    /**
     * 思路：
     * 前序遍历的第一个结点就是root结点
     * 根据root 结点找到中序遍历的数组中的根结点 可以得出 【左子树|根结点|右子树】
     * 然后递归 通过前序遍历和中序遍历一直找出子树的根结点、左子树、右子树
     * */

    HashMap<Integer, Integer> map = new HashMap<>();// 标记中序遍历
    int[] preorder;// 保留先序遍历
    int[] afterorder;

    public TreeNode buildTree(int[] preorder, int[] inorder){
        this.preorder = preorder;
        for (int i = 0; i < preorder.length; i++) {
            map.put(inorder[i],i);
        }
        return recursive(0,0,inorder.length-1);
    }


    /**
     * @param pre_root_idx 先序遍历的索引
     * @param in_left_idx 中序遍历数组的起点
     * @param in_right_idx 中序遍历数组的终点
     *
     * @decription 我们只要先序遍历的起点就能找到 先序遍历的根结点
     * 但是我们需要中序遍历的起点和终点，才能在这个范围内去找到根结点
     * */
    public TreeNode recursive(int pre_root_idx, int in_left_idx, int in_right_idx){
        // 中序遍历的左边 > 右边 表示已经结束了
        if(in_left_idx > in_right_idx){
            return null;
        }
        // 构建根结点
        TreeNode root = new TreeNode(preorder[pre_root_idx]);

        // pre_root_idx是先序遍历中根结点的索引
        // preorder[pre_root_idx]这个是根结点的值，这里就是拿到中序遍历中根结点的索引
        int idx = map.get(preorder[pre_root_idx]);// 中序遍历中 根结点的索引

        /**
         * 左子树的前序遍历中根结点就是当前根结点位置+1
         * 左子树中序遍历的：
         * 左边边界就是left
         * 右边边界就是中序遍历的根结点idx-1
         *
         * */
        root.left = recursive(pre_root_idx+1,in_left_idx,idx-1);

        /**
         *
         * 右子树先序遍历的根结点位置 就是当前根结点+左子树的数量 + 1
         * 左子树数量=（中序遍历的根结点位置-1 - 中序遍历左子树的第一个结点位置）
         *
         * 中序遍历的右子树的左边第一个元素 idx+1
         *
         * 右边界 right
         * */
        root.right = recursive(pre_root_idx + (idx - in_left_idx) + 1,
                idx+1 , in_right_idx);

        return root;
    }

    public int[] after(TreeNode root){

        return null;
    }
}
